package ljl.alg.jianzhioffer.round2;

/**
 * 摊牌了，不会做
 * 1. 暴力法，估计大小；如果是 n方复杂度，n 能到五万，这一般不能接受
 * 2. 归并排序不会写，需要复习复习了
 * 3. 想了想，基数排序也是不会的
 * 4. 希尔排序自然也写不出来
 * 5. 目前只会堆排、快排、插入排；不会基数、希尔、归并，请及时复习
 * */
public class _51_reverse_pairs {

    int[] nums, tmp;
    public int reversePairs_final(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length - 1);
    }
    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = nums[k];
        for (int k = l; k <= r; k++) {
            // i 越界，拷贝 j
            if (i == m + 1)
                nums[k] = tmp[j++];
            // j 越界，或 i 比 j 值大，拷贝 i
            else if (j == r + 1 || tmp[i] <= tmp[j])
                nums[k] = tmp[i++];
            // j 没越界，且比 i 值小，拷贝 j，记录逆序数
            // 注意到逆序数不是 1，而是 m - i + 1
            // ？我日
            else {
                nums[k] = tmp[j++];
                // 4 5      2 3
                // i        j     有 4 个是吧
                // 由于只遍历一次，如果发现 j 比 i 小了，j 比 i 后面的数都小，后面几个数呢？包含 i？m - i + 1 个数
                // 所以。
                res += m - i + 1; // 统计逆序对
            }
        }
        return res;
    }
    
    
    public int reversePairs(int[] nums) {
        return merge(nums, new int[nums.length], 0, nums.length - 1);
    }
    int merge(int[] nums, int[] tmp, int l, int r) {
        // 这里肯定会出现 l > r 的，所以。
        if (l >= r)
            return 0;
        int m = (l + r) >>> 1;
        int res = merge(nums, tmp, l, m) + merge(nums, tmp, m + 1, r);
        System.arraycopy(nums, l, tmp, l, r - l + 1);
    
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++) {
            if (i > m)
                nums[k] = tmp[j++];
            else if (j > r || tmp[i] <= tmp[j])
                nums[k] = tmp[i++];
            else {
                nums[k] = tmp[j++];
                res += m - i + 1;
            }
        }
        return res;
    }
    
}
